package leetcode15

// 排序后双指针
func threeSum(nums []int) [][]int {
	var res [][]int = [][]int{}
	if len(nums) < 3 {
		return res
	}
	nums = quickSort(nums)
	var (
		left  int
		right int
	)

	for i := 0; i < len(nums); i++ {
		if i >= 1 && nums[i-1] == nums[i] {
			continue
		}

		left = i + 1
		right = len(nums) - 1

		for left = i + 1; left < right; left++ {

			if left > i+1 && nums[left] == nums[left-1] {
				continue
			}

			for left < right && nums[i]+nums[left]+nums[right] > 0 {
				right--
			}

			if left < right && nums[i]+nums[left]+nums[right] == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
			}
		}
	}

	return res
}

func quickSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	mid := nums[0]
	var (
		left  []int
		mids  []int
		right []int
	)
	for i := 0; i < len(nums); i++ {
		if nums[i] < mid {
			left = append(left, nums[i])
		} else if nums[i] > mid {
			right = append(right, nums[i])
		} else {
			mids = append(mids, mid)
		}
	}
	return append(append(quickSort(left), mids...), quickSort(right)...)
}
